public class ReversePairs{
    //交换逆序对
    int[] tmp;

    public int code(int[] record) {
        int n = record.length;
        tmp = new int[n];
        return mergerSort(record, 0, n - 1);
    }

    public int mergerSort(int[] nums, int left, int right){
        if(left >= right){
            return 0;
        }

        int ret = 0;  //返回值
        int mid = (left + right) / 2;

        ret += mergerSort(nums, left, mid);   //排序左边
        ret += mergerSort(nums, mid + 1, right);   //排序右边

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right){
            if (nums[cur1] <= nums[cur2]){
                tmp[i++] = nums[cur1++];
            }else{
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }

        //处理一下排序
        while (cur1 <= mid){
            tmp[i++] = nums[cur1++];
        }

        while (cur2 <= right){
            tmp[i++] = nums[cur2++];
        }

         for (int j = left; j <= right; j++){
             nums[j] = tmp[j - left];
         }

        return ret;
    }

    public static void main(String[] args) {
        ReversePairs test = new ReversePairs();
        System.out.println(test.code(new int[]{9, 7, 5, 6, 4}));
    }
}
